/*
 * 本文件提供实现Decaf编译器所需要的BYACC脚本。
 * 在第一阶段中你需要补充完整这个文件中的语法规则。
 * 请参考"YACC--Yet Another Compiler Compiler"中关于如何编写BYACC脚本的说明。
 * 
 * Keltin Leung
 * DCST, Tsinghua University
 */
 
%{
package decaf.frontend;

import decaf.tree.Tree;
import decaf.tree.Tree.*;
import decaf.error.*;
import java.util.*;
%}

%Jclass Parser
%Jextends BaseParser
%Jsemantic SemValue
%Jimplements ReduceListener
%Jnorun
%Jnodebug
%Jnoconstruct

%token VOID   BOOL  INT   STRING  CLASS 
%token NULL   EXTENDS     THIS     WHILE   FOR   
%token IF     ELSE        RETURN   BREAK   NEW
%token PRINT  READ_INTEGER         READ_LINE
%token LITERAL
%token IDENTIFIER	  AND    OR    STATIC  INSTANCEOF
%token LESS_EQUAL   GREATER_EQUAL  EQUAL   NOT_EQUAL
%token '+'  '-'  '*'  '/'  '%'  '='  '>'  '<'  '.'
%token ','  ';'  '!'  '('  ')'  '['  ']'  '{'  '}'

%left ','
%right '='
%left OR 
%left AND 
%nonassoc EQUAL NOT_EQUAL
%nonassoc LESS_EQUAL GREATER_EQUAL '<' '>' INSTANCEOF
%left  '+' '-'
%left  '*' '/' '%'
%left  NEW
%right UMINUS '!' 
%left '[' '.' ']' '(' ')'
%left EMPTY

%start Program

%%
Program			:	ClassList
					{
						tree = new Tree.TopLevel($1.clist, $1.loc);
					}
				;

ClassList       :	ClassList ClassDef
					{
						$$.clist.add($2.cdef);
					}
                |	ClassDef
                	{
                		$$.clist = new ArrayList<Tree.ClassDef>();
                		$$.clist.add($1.cdef);
                	}
                ;

VariableDef     :	Variable ';'
				;

Variable        :	Type IDENTIFIER
					{
						$$.vdef = new Tree.VarDef($2.ident, $1.type, $2.loc);
					}
				;
				
Type            :	INT	//type def 
					{
						$$.type = new Tree.TypeIdent(Tree.INT, $1.loc);	
					}
				|	VOID
					{
						$$.type = new Tree.TypeIdent(Tree.VOID, $1.loc);
					}
				|	BOOL
					{
						$$.type = new Tree.TypeIdent(Tree.BOOL, $1.loc);
					}
				|	STRING
					{
						$$.type = new Tree.TypeIdent(Tree.STRING, $1.loc);
					}
				|	CLASS IDENTIFIER
					{
						$$.type = new Tree.TypeClass($2.ident, $2.loc);
					}
				|	Type '[' ']'
					{
						$$.type = new Tree.TypeArray($1.type, $1.loc);
					}
                ;

ClassDef        :	CLASS IDENTIFIER ExtendsClause '{' FieldList '}'	//class def
					{
						$$.cdef = new Tree.ClassDef($2.ident, $3.ident, $5.flist, $1.loc);
					}
                ;

ExtendsClause	:	EXTENDS IDENTIFIER
					{
						$$.ident = $2.ident;
					}
                |	/* empty */		//extendsclause def
                	{
                		$$ = new SemValue();
                	}
                ;

FieldList       :	FieldList VariableDef
					{
						$$.flist.add($2.vdef);
					}
				|	FieldList FunctionDef
					{
						$$.flist.add($2.fdef);
					}
                |	/* empty */
                	{
                		$$ = new SemValue();	//def
                		$$.flist = new ArrayList<Tree>();	//fieldlist def
                	}
                ;
 
Formals         :	VariableList
                |	/* empty */
                	{
                		$$ = new SemValue();
                		$$.vlist = new ArrayList<Tree.VarDef>(); 
                	}
                ;

VariableList    :	VariableList ',' Variable
					{
						$$.vlist.add($3.vdef);
					}
                |	Variable
                	{
                		$$.vlist = new ArrayList<Tree.VarDef>();	//vl def
						$$.vlist.add($1.vdef);
                	}
                ;

FunctionDef    :	STATIC Type IDENTIFIER '(' Formals ')' StmtBlock
					{
						$$.fdef = new MethodDef(true, $3.ident, $2.type, $5.vlist, (Block) $7.stmt, $3.loc);
					}
				|	Type IDENTIFIER '(' Formals ')' StmtBlock
					{
						$$.fdef = new MethodDef(false, $2.ident, $1.type, $4.vlist, (Block) $6.stmt, $2.loc);
					}
                ;

StmtBlock       :	'{' StmtList '}'
					{
						$$.stmt = new Block($2.slist, $1.loc);
					}
                ;
	
StmtList        :	StmtList Stmt
					{
						$$.slist = $1.slist;
						$$.slist.add($2.stmt);
					}
                |	/* empty */
                	{
                		$$ = new SemValue();
                		$$.slist = new ArrayList<Tree>();
                	}
                ;

Stmt		    :	VariableDef
					{
						$$.stmt = $1.vdef;
					}
				|	SimpleStmt ';'
					{
						$$.stmt = $1.stmt;
					}
				|	IfStmt
					{
						$$.stmt = $1.stmt;
					}
				|	WhileStmt
					{
						$$.stmt = $1.stmt;
					}
				|	ForStmt
					{
						$$.stmt = $1.stmt;
					}
				|	BreakStmt ';'
					{
						$$.stmt = $1.stmt;
					}
				|	ReturnStmt ';'
					{
						$$.stmt = $1.stmt;
					}
				|	PrintStmt ';'
					{
						$$.stmt = $1.stmt;
					}
				|	StmtBlock
					{
						$$.stmt = $1.stmt;
					}
                ;
                
SimpleStmt		:	LValue '=' Expr
					{
						$$.stmt = new Assign($1.lvalue,$3.expr,$1.loc);
					}
				|	Call
					{
						$$.stmt = $1.expr;
					}
				|	/* empty */
					{
                		$$.stmt = new Skip($1.loc);         								
					}
				;
				
LValue			:	Expr '.' IDENTIFIER
					{
						$$.lvalue = new Ident($1.expr,$3.ident,$3.loc);
					}
				|	IDENTIFIER
					{
						$$.lvalue = new Ident(null,$1.ident,$1.loc);
					}
				|	Expr '[' Expr ']'
					{
						$$.lvalue = new Indexed($1.expr,$3.expr,$3.loc);
					}
				;
				
Call			:	Expr '.' IDENTIFIER '(' Actuals ')'
					{
						$$.expr = new Apply($1.expr,$3.ident,$5.elist,$1.loc);
					}
				|	IDENTIFIER '(' Actuals ')'
					{
						$$.expr = new Apply(null,$1.ident,$3.elist,$1.loc);
					}
				;
				
Actuals			:	ExprList
					{
						$$.elist = $1.elist;
					}
				|	/* empty */
					{
                		$$= new SemValue();          
                		$$.elist = new ArrayList<Tree.Expr>();     													
					}	
				;
					
ExprList    	:	ExprList ',' Expr
					{
						$$.elist = $1.elist;
						$$.elist.add($3.expr);
					}
                |	Expr
					{
						$$.elist = new ArrayList<Tree.Expr>();
						$$.elist.add($1.expr);
					}
				;
				
ForStmt			:	FOR '(' SimpleStmt ';' BoolExpr ';' SimpleStmt ')' Stmt
					{
						$$.stmt = new ForLoop($3.stmt,$5.expr,$7.stmt,$9.stmt,$1.loc);
					}
				;
					
WhileStmt		:	WHILE '(' BoolExpr ')' Stmt
					{
						$$.stmt = new WhileLoop($3.expr,$5.stmt,$1.loc);
					}
				;
				
IfStmt			:	IF '(' BoolExpr ')' Stmt 
					{
						$$.stmt = new If($3.expr,$5.stmt,null,$1.loc);
					}
				|	IF '(' BoolExpr ')' Stmt ELSE Stmt
					{
						$$.stmt = new If($3.expr,$5.stmt,$7.stmt,$1.loc);
					}
				;
				
ReturnStmt		:	RETURN 
					{
						$$.stmt = new Return(null,$1.loc);
					}
				|	RETURN Expr
					{
						$$.stmt = new Return($2.expr,$1.loc);
					}
				;
				
BreakStmt		:	BREAK
					{
						$$.stmt = new Break($1.loc);
					}
				;
				
PrintStmt		:	PRINT '(' ExprList ')'
					{
						$$.stmt = new Print($3.elist,$1.loc);
					}
				;
				
BoolExpr		:	Expr
					{
						$$.expr = $1.expr;
					}
				;
				
Expr			:	LITERAL
					{
						$$.expr = new Literal($1.typeTag,$1.literal,$1.loc);
					}
				|	LValue
					{
						$$.expr =  $1.lvalue;
					}
				|	THIS
					{
						$$.expr = new ThisExpr($1.loc);
					}
				|	Call
					{
						$$.expr = $1.expr;
					}
				|	'('	Expr ')'
					{
						$$.expr = $2.expr;
					}
				|	Expr '+' Expr
					{
						$$.expr = new Binary(Tree.PLUS,$1.expr,$3.expr,$1.loc);
					}
				|	Expr '-' Expr
					{
						$$.expr = new Binary(Tree.MINUS,$1.expr,$3.expr,$1.loc);
					}
				|	Expr '*' Expr
					{
						$$.expr = new Binary(Tree.MUL,$1.expr,$3.expr,$1.loc);
					}
				|	Expr '/' Expr
					{
						$$.expr = new Binary(Tree.DIV,$1.expr,$3.expr,$1.loc);
					}
				|	Expr '%' Expr
					{
						$$.expr = new Binary(Tree.MOD,$1.expr,$3.expr,$1.loc);
					}
				|	'-'	Expr
					{
						$$.expr = new Unary(Tree.NEG,$2.expr,$1.loc);
					}
				|	Expr '<' Expr
					{
						$$.expr = new Binary(Tree.LT,$1.expr,$3.expr,$1.loc);
					}
				|	Expr LESS_EQUAL Expr
					{
						$$.expr = new Binary(Tree.LE,$1.expr,$3.expr,$1.loc);
					}
				|	Expr '>' Expr
					{
						$$.expr = new Binary(Tree.GT,$1.expr,$3.expr,$1.loc);
					}
				|	Expr GREATER_EQUAL Expr
					{
						$$.expr = new Binary(Tree.GE,$1.expr,$3.expr,$1.loc);
					}
				|	Expr EQUAL Expr
					{
						$$.expr = new Binary(Tree.EQ,$1.expr,$3.expr,$1.loc);
					}
				|	Expr NOT_EQUAL Expr
					{
						$$.expr = new Binary(Tree.NE,$1.expr,$3.expr,$1.loc);
					}
				|	Expr AND Expr
					{
						$$.expr = new Binary(Tree.AND,$1.expr,$3.expr,$1.loc);
					}
				|	Expr OR Expr
					{
						$$.expr = new Binary(Tree.OR,$1.expr,$3.expr,$1.loc);
					}
				|	'!' Expr 
					{
						$$.expr = new Unary(Tree.NOT,$2.expr,$1.loc);
					}
				|	READ_INTEGER '(' ')'
					{
						$$.expr = new ReadIntExpr($1.loc);
					}
				|	READ_LINE '(' ')'
					{
						$$.expr = new ReadLineExpr($1.loc);
					}
				|	NEW IDENTIFIER '(' ')'
					{
						$$.expr = new NewClass($2.ident,$1.loc);
					}
				|	NEW Type '[' Expr ']'
					{
						$$.expr = new NewArray($2.type,$4.expr,$1.loc);
					}
				|	INSTANCEOF '(' Expr ',' IDENTIFIER ')'
					{
						$$.expr = new TypeTest($3.expr,$5.ident,$1.loc);
					}
				|	'(' CLASS IDENTIFIER ')' Expr
					{
						$$.expr = new TypeCast($3.ident,$5.expr,$1.loc);
					}
				|	NULL
					{
						$$.expr = new Null($1.loc);
					}
				;				
%%
    
	/**
	 * 打印当前归约所用的语法规则<br>
	 * 请勿修改。
	 */
    public boolean onReduce(String rule) {
		if (rule.startsWith("$$"))
			return false;
		else
			rule = rule.replaceAll(" \\$\\$\\d+", "");

   	    if (rule.endsWith(":"))
    	    System.out.println(rule + " <empty>");
   	    else
			System.out.println(rule);
		return false;
    }
    
    public void diagnose() {
		addReduceListener(this);
		yyparse();
	}
